package com.zp.self.module.level_4_算法练习.数据结构.数组;

import java.util.LinkedList;

/**
 * @author By ZengPeng
 */
public class 力扣_57_插入区间 {
    //测试
    public static void main(String[] args) {
        int[][] insert;
        insert = new 力扣_57_插入区间().insert(new int[][]{{1, 5}}, new int[]{6, 8});
        for (int[] ints : insert) System.out.print("["+ints[0]+","+ints[1]+"],");
        System.out.println();

        insert = new 力扣_57_插入区间().insert(new int[][]{{6, 8}}, new int[]{1, 5});
        for (int[] ints : insert) System.out.print("["+ints[0]+","+ints[1]+"],");
        System.out.println();

        insert = new 力扣_57_插入区间().insert(new int[][]{{1, 3}, {6, 9}}, new int[]{2, 5});
        for (int[] ints : insert) System.out.print("["+ints[0]+","+ints[1]+"],");
        System.out.println();

        insert = new 力扣_57_插入区间().insert(new int[][] {{3,5},{12,16}}, new int[]{6, 6});
        for (int[] ints : insert) System.out.print("["+ints[0]+","+ints[1]+"],");
        System.out.println();


        insert = new 力扣_57_插入区间().insert(new int[][] {{1,2},{3,5},{6,7},{8,10},{12,16}}, new int[]{4, 8});
        for (int[] ints : insert) System.out.print("["+ints[0]+","+ints[1]+"],");
        System.out.println();

        insert = new 力扣_57_插入区间().insert(new int[][] {}, new int[]{5, 7});
        for (int[] ints : insert) System.out.print("["+ints[0]+","+ints[1]+"],");
        System.out.println();

        insert = new 力扣_57_插入区间().insert(new int[][] {{1,5}}, new int[]{2, 3});
        for (int[] ints : insert) System.out.print("["+ints[0]+","+ints[1]+"],");
        System.out.println();

        insert = new 力扣_57_插入区间().insert(new int[][] {{1,5}}, new int[]{2, 7});
        for (int[] ints : insert) System.out.print("["+ints[0]+","+ints[1]+"],");
        System.out.println();
    }

    /**
    题目：给你一个 无重叠的 ，按照区间起始端点排序的区间列表。
     在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

     示例 1：
     输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
     输出：[[1,5],[6,9]]

     示例 2：
     输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
     输出：[[1,2],[3,10],[12,16]]
     解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

    分析：【perfect】可以得出目前已经拍好序了，不用再排序了  [状态不好，用时过长]
       1.标记是已经插入？
         总是当 intervals[i][0]>end时，后续不可能再有交集 ，这里要看标记是否已经插入。
       执行用时：1 ms, 在所有 Java 提交中击败了94.98%的用户

    边界值 & 注意点：
       1.[[1,5]] ,[6,8]
       2.[[3,5],[12,15]],[6,6]
     **/
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int start=newInterval[0],end =newInterval[1];
        boolean cross =false;//false未添加，true 已添加
        LinkedList<int[]> res = new LinkedList<>();
        for (int i = 0; i < intervals.length; i++) {
            if(intervals[i][0]>end){ //不可能 再有交集 ，这里要看看是否该添加值了
                if(!cross){
                    res.add(new int[]{start,end});
                    cross =true;
                }
                res.add(intervals[i]);
                continue;
            }
            if( intervals[i][1]<start){ //与[start,end]无交集的情况,后续可能还会有机会
                res.add(intervals[i]);
            }else {
                end = Math.max(end,intervals[i][1]);  //与[start,end]有交集的情况
                start = Math.min(start,intervals[i][0]);
            }
        }
        if(!cross)
            res.add(new int[]{start,end});
        return  res.toArray(new int[res.size()][]);
    }
}
